import random
from typing import *


class Solution:
    def maxmiumScore(self, cards: List[int], cnt: int) -> int:
        cards.sort(reverse=True)
        tot = 0
        j, o = [], []
        for i in range(cnt):
            tot += cards[i]
            if cards[i] & 1 == 1:
                j.append(cards[i])
            else:
                o.append(cards[i])
        if tot & 1 == 0:
            return tot
        j2, o2 = [], []
        for i in range(cnt, len(cards)):
            if cards[i] & 1 == 1:
                j2.append(cards[i])
            else:
                o2.append(cards[i])
        ans1, ans2 = 0, 0
        if len(j2) > 0 and len(o) > 0:
            ans1 = tot - o[-1] + j2[0]
        if len(o2) > 0 and len(j) > 0:
            ans2 = tot - j[-1] + o2[0]
        return max(ans1, ans2)


s = Solution()
print(s.maxmiumScore(cards=[9, 5, 9, 1, 6, 10, 3, 4, 5, 1], cnt=2))
print(s.maxmiumScore(cards=[1, 2, 8, 9], cnt=3))

t = []
for i in range(20):
    t.append(random.randint(1, 200))
print(t)
